#include <stdio.h>    /* for printf */
#include <stdlib.h>   /* for malloc */

/* this should be removed and defined in the using C file: should be a pointer to the actoa data */
#define MY_LIST_DATA_TYPE int

void free_LLIST_data(MY_LIST_DATA_TYPE data);
/* end of remove */
 
typedef struct node {
	MY_LIST_DATA_TYPE data;
	struct node *next; /* pointer to next element in list */
} LLIST;
 
LLIST *list_add(LLIST **p, MY_LIST_DATA_TYPE i);  /* Function definition to add an element */
void list_remove(LLIST **p);        /* Function definition to remove element */
LLIST **list_search(LLIST **n, MY_LIST_DATA_TYPE i); /* Function definition to search the list */

/****************************************************************/
/*  Function: Add an element to our list                        */
/*                                                              */
/*   Parameters: **p is the node that we wish to insert at.     */
/*               if the node is the null insert it at the beginning    */
/*               Other wise put it in the next space                   */
 
 
LLIST *list_add(LLIST **p, MY_LIST_DATA_TYPE i)
{
	if (p == NULL)           /*checks to see if the pointer points somewhere in space*/
		return NULL;
 
	LLIST *n = (LLIST *)malloc(sizeof(LLIST));   /* creates a new node of the correct data size */
	if (n == NULL)
		return NULL;
 
	n->next = *p; /* the previous element (*p) now becomes the "next" element */
	*p = n;       /* add new empty element to the front (head) of the list */
	n->data = i;
 
	return *p;
}
 
void list_remove(LLIST **p) /* remove head */
{
	if (p != NULL && *p != NULL)
	{
		LLIST *n = *p;
		*p = (*p)->next;
		if (n->data != NULL)
			free_LLIST_data(n->data);
		free(n);
	}
}
 
LLIST **list_search(LLIST **n, int i)
{
	if (n == NULL)
		return NULL;
 
	while (*n != NULL)
	{
		if ((*n)->data == i)
		{
			return n;
		}
		n = &(*n)->next;
	}
	return NULL;
}
 
void list_print(LLIST *n)
{
	if (n == NULL)
	{
		printf("list is empty\n");
	}
	while (n != NULL)
	{
		printf("print %p %p %d\n", n, n->next, n->data);
		n = n->next;
	}
}
 
int main(void)
{
	LLIST *n = NULL;
 
	list_add(&n, 0); /* list: 0 */
	list_add(&n, 1); /* list: 1 0 */
	list_add(&n, 2); /* list: 2 1 0 */
	list_add(&n, 3); /* list: 3 2 1 0 */
	list_add(&n, 4); /* list: 4 3 2 1 0 */
	list_print(n);
	list_remove(&n);                 /* remove first (4) */
	list_remove(&n->next);           /* remove new second (2) */
	list_remove(list_search(&n, 1)); /* remove cell containing 1 (first) */
	list_remove(&n->next);           /* remove second to last node (0) */
	list_remove(&n);                 /* remove last (3) */
	list_print(n);
 
	return 0;
}

